In a transmission of data over a cell switched digital communication network, such as an asynchronous transfer mode or ATM network, problems arise when multiple sources send data cells at widely varying rates through a switch node or link of the network at an aggregated rate which taxes the ability of that switch node or link to handle the data. Congestion occurs at the node of a network when data arrives at the node at a rate exceeding the rate at which the node can process and forward the data to other nodes. The excess data then accumulates in buffer storage at the node, which fills at a rate which is the difference between the arrival rate and the processing and forwarding rate. If the congestion persists for long periods of time, the buffer storage will be filled to maximum capacity and any additional data must be discarded.
In an effort to minimize such data loss, a rate-based flow control system has been disclosed to prevent or inhibit excess data from entering the network. In a rate-based system, the rate at which the data is permitted to enter the network is controlled to not exceed a certain transmission rate, and this transmission rate is adjusted via a feedback signal from a network reflecting the congestion of the network. One such rate controlled system is described in an ATM Forum document #95-0013R2 entitled "Draft Version 3.0 of ATM Forum Traffic Management Specification Version 4.0" authored by Shirish S. Sathaye and David Hughes, April 1995.
One key element in implementing the above described rate-based flow control system is a traffic shaping unit which delays the traffic generated at a source and injects it at a rate no larger than that specified by a flow control scheme. One way to implement such a traffic shaping function is to use a timing chain. A timing chain is composed of an array of slots, with each slot representing one cell time defined as the time needed to transmit one cell of data at the full link transmission speed. A current time pointer points to a slot representing the current time or the current slot to cause cells at that slot to be transmitted, with the time pointer moving forward one slot every cell time. To control cell transmission rate where the rate is under R cells every cell time, at a time when a cell is transmitted, a new cell is scheduled in a slot which is 1/R slots away from the current slot. That is to say the cell is scheduled to be transmitted at a time which is delayed from the current time by a time equal to 1/R cell times. When the current time pointer moves to a slot, all cells queued at the slot become eligible for transmission.
However, one major problem with the above described timing chain approach is its high cost in supporting low rate traffic shaping which needs to delay cells for a long period of time. When the transmission rate R is small, 1/R becomes large. Thus, a timing chain needs a large number of slots, i.e., 1/R slots, to shape a transmission rate of R, making the system very expensive. Low data rate traffic in general refers to the transmission of text, as opposed to high data rate traffic such as full frame video. It is important that any network be capable of supporting both text transfer as well as video transmission as efficiently as possible, and be capable of reducing transmission rates of sources when the network is congested.